/**
 * @param {string[]} words
 * @param {character[]} letters
 * @param {number[]} score
 * @return {number}
 */
var maxScoreWords = function (words, letters, score) {
  let scores = []
  let map = new Map()
  let eachRoundScore = 0
  for (const letter of letters) {
    map.set(letter, map.has(letter) ? map.get(letter) + 1 : 1)
  }
  function backtracking(index) {
    for (let i = index; i < words.length; i++) {
      let wordScore = getScore(words[i])
      if (wordScore == 0) continue
      eachRoundScore += wordScore
      scores.push(eachRoundScore)
      backtracking(i + 1)
      eachRoundScore -= wordScore
      reStoreScore(words[i])
    }
  }

  function getScore(word) {
    let res = 0
    for (let i = 0; i < word.length; i++) {
      if (!map.has(word[i])) {
        res = 0
        break
      } else {
        if (map.get(word[i]) == 0) {
          res = 0
          break
        } else {
          res += score[map.get(word[i]).charCodeAt() - 'a'.charCodeAt()]
          map.set(word[i], map.get(word[i]) - 1)
        }
      }
    }
    if (res == 0) {
      reStoreScore(word.subString(0,i))
    }

    return res
  }

  function reStoreScore(word) {
    for(const letter of word){
      map.set(letter, map.get(letter) + 1)
    }
  }

  backtracking(0)
  return [...scores]
}

maxScoreWords(
  ['dog', 'cat', 'dad', 'good'],
  ['a', 'a', 'c', 'd', 'd', 'd', 'g', 'o', 'o'],
  [1, 0, 9, 5, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
)
